package com.jxb.dp;

/**
 * 输入：[7,1,5,3,6,4]
 * 输出：5
 * 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
        [7,	1,	5,	3,	6,	4]
        0	1	2	3	4	5

 不持股0	0	0	4	4	5	5

 持股1  -7	-1	-1	-1	-1	-1

 不持股：dp[i][j] = max(dp[i-1][0],dp[i-1][1] + prices[i])
 持股：dp[i][j] = max(dp[i-1][1],-prices[i])
 dp[0][0] = 0，dp[0][1] = -7
 dp[1][0] = 0，dp[1][1] = -1
 dp[2][0] = 4，dp[2][1] = -1
 dp[3][0] = 4，dp[3][1] = -1
 dp[4][0] = 5，dp[4][1] = -1
 dp[5][0] = 5，dp[5][1] = -1
 不持股所得的利润：
 dp[len-1,0]=5
 */
public class BuyStock_121 {
    public static void main(String[] args) {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit0(prices));
    }


    //1:确定状态转移公式：newRes = max(res,res+nums[i])
    //2:初始化dp数组：
        //不持股：dp[i][j] = max(dp[i-1][0],dp[i-1][1] + prices[i])
        //持股：dp[i][j] = max(dp[i-1][1],-prices[i])
        //i:第几天，j:是否持股（0：表示当天不持股，1：表示当天持股）
        //dp[0][0] = 0;dp[0][1] = -prices[0](初始现金为0买入股票)；dp[i][0]表示今天不持股；dp[i-1][0]表示昨天持股；dp[i-1][1]表示昨天持股，今天卖出股票
    //3:根据条件开始遍历，并实现状态转移公式
    public static int maxProfit0(int[] prices) {
        if (prices.length<2) {
            return 0;
        }
        //初始化dp数组
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        //遍历原数组
        for (int i = 1;i<prices.length;i++) {
            //获取上次不持股或者持股的最大值
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1] + prices[i]);
            //对此次持股进行赋值：上次的持股和这次的股价的负值中的最大值
            dp[i][1] = Math.max(dp[i-1][1],-prices[i]);
        }
        return dp[prices.length - 1][0];
    }

    //其他的方法
    //时间复杂度O(n),空间复杂度O(1)
    public static int maxProfit1(int[] prices) {
        int max = 0;
        int min = prices[0];
        //newRes = max(res,res+nums[i])
        for (int i = 0;i<prices.length;i++) {
            if (prices[i] > min) {
                max = Math.max(max,prices[i] - min);
            }else {
                min = prices[i];
            }
        }
        return max;
    }

}
